# coding: utf-8

'''
@autor1: João Batista nº5479
@autor2: Luis Cabaço nº5606
@data Inicio: 28/05/2013
@data Fim: 11/06/2013
'''

import algoritmosOrdenacao as alg

import datetime, time
import random
import csv
import numpy 


def resultados_output_csv(dicionario):
	'''
		Metodo para criar criar os ficheiros com os resultados dos tempos obtidos
		em cada algoritmo nas diferentes listas e as estastiticas dos mesmos.

		Args:
			dicionario: dicionario de algoritmos e a a respetivas listas de tempos
	'''

	ficheiroTempos = 'tempos.csv'
	ficheiroCalculos = 'calculos.csv'

	ficheiroCsvTempos=open(ficheiroTempos, "wb") # abrir o ficheiro csv
	escrivaoTempos = csv.writer(ficheiroCsvTempos, delimiter =',') # writer

	ficheiroCsvCalculos=open(ficheiroCalculos, "wb") # abrir o ficheiro csv
	escrivaoCalculos = csv.writer(ficheiroCsvCalculos, delimiter =',') # writer

	escrivaoTempos.writerow(["#Organização do Ficheiro"])
	escrivaoTempos.writerow(["#Algoritmo"])
	escrivaoTempos.writerow(["#Nº Elementos Lista"])
	escrivaoTempos.writerow(["#Lista de tempos"])

	escrivaoCalculos.writerow(["#Organização do Ficheiro"])	
	escrivaoCalculos.writerow(["#Algoritmo"])	
	escrivaoCalculos.writerow(["#Nº Elementos Lista"])	
	escrivaoCalculos.writerow(["#média", "mediana", "desvio padrão"])

	#Ciclo para percorrer cada algoritmo no dicionario
	for algoritmo in dicionario:

		escrivaoTempos.writerow([algoritmo])
		escrivaoCalculos.writerow([algoritmo])

		listasResultados = dicionario[algoritmo]

		#Ciclo para percorrer cada lista dentro do algoritmo
		for lista in listasResultados:

			tamanhoLista = lista[:1]
			temposAlgoritmo = lista[1:]

			escrivaoTempos.writerow(tamanhoLista)
			escrivaoTempos.writerow(temposAlgoritmo)

			mediaAlgoritmo = numpy.mean(temposAlgoritmo)
			medianaAlgoritmo = numpy.median(temposAlgoritmo)
			desvioPadraoAlgoritmo = numpy.std(temposAlgoritmo, dtype=numpy.float64)

			escrivaoCalculos.writerow(tamanhoLista)
			escrivaoCalculos.writerow([round(mediaAlgoritmo, 2), round(medianaAlgoritmo, 2), round(desvioPadraoAlgoritmo, 2)])
			pass
		pass
	pass

def resultados_output_visual(dicionario):
	'''
		Metodo para mostrar as estatisticas calculadas atravez dos tempos de execuçao
		no terminal.

		Args:
			dicionario: dicionario de algoritmos e a a respetivas listas de tempos
	'''

	for algoritmo in dicionario:

		print '\nResultados para:', algoritmo

		listasResultados = dicionario[algoritmo]

		for lista in listasResultados:

			tamanhoLista = lista[:1]
			temposAlgoritmo = lista[1:]

			mediaAlgoritmo = numpy.mean(temposAlgoritmo)
			medianaAlgoritmo = numpy.median(temposAlgoritmo)
			desvioPadraoAlgoritmo = numpy.std(temposAlgoritmo, dtype=numpy.float64)
			varianciaAlgoritmo = numpy.var(temposAlgoritmo, dtype=numpy.float64)

			print 'Listas com', tamanhoLista[0], 'elementos!'
			print 'Media tempos:', mediaAlgoritmo
			print 'Mediana tempos:', medianaAlgoritmo
			print 'Desvio Padrão Algoritmos:', desvioPadraoAlgoritmo
			print 'Variancia Algoritmos:', varianciaAlgoritmo, "\n"
			pass
		pass
	pass

def gerador_listas_random(numeroElementos):
	'''
		Metodo para gerar uma lista random com "x" elementos.

		Args:
			numeroElementos: numero de elementos da lista

		Returns:
			listaRandom: lista de numeros aleatorios com "x" elementos
	'''

	listaRandom = []

	for x in xrange(0, numeroElementos):
				inteiroAleatorio = random.randint(0, numeroElementos*10)
				listaRandom.append(inteiroAleatorio)
				pass

	return listaRandom

def main():
	'''
		Metodo principal da aplicacao.
	'''

	algoritmos = alg.Algoritmos()

	#Para guardar os tempos será utilizado um dicionário em que
	#utilizamos o nome do algoritmo como chave e guardará um
	#array com os resultados
	dictAlgoritmo = dict()
	dictAlgoritmo['Quick-Sort'] = []
	dictAlgoritmo['Merge-Sort'] = []
	dictAlgoritmo['Insertion-Sort'] = []
	dictAlgoritmo['Bubble-Sort'] = []
	dictAlgoritmo['Heap-Sort'] = []
	dictAlgoritmo['Shell-Sort'] = []
	dictAlgoritmo['Selection-Sort'] = []
	dictAlgoritmo['Bucket-Sort'] = []

	print "\n## Algoritmos de ordenacao ##"
	tamanhos = [10, 50, 100, 250, 500, 750, 1000]

	repeticoesLista = 2000

	#ciclo para tamanhos das listas
	for tamanho in tamanhos:

		print "A correr os algoritmos para listas com", tamanho, 'elementos!'
		print 'Inicio:', time.strftime('%X')

		#listas com resultados
		resultadosQuick = []
		resultadosMerge = []
		resultadosInsertion = []
		resultadosBubble = []
		resultadosHeap = []
		resultadosShell = []
		resultadosSelection = []
		resultadosBucket = []

		#adicionando o nº de elementos de uma lista
		#esta lista será usada mais abaixo para calcular os resultados
		#para cada algoritmo.
		resultadosQuick.append(tamanho)
		resultadosMerge.append(tamanho)
		resultadosInsertion.append(tamanho)
		resultadosBubble.append(tamanho)
		resultadosHeap.append(tamanho)
		resultadosShell.append(tamanho)
		resultadosSelection.append(tamanho)
		resultadosBucket.append(tamanho)
		
		#ciclo para calcular os tempos de execução de cada algoritmo para
		#poder calcular os valores médios e proceder à verificação da
		#performance do algorimo
		for y in xrange(0, repeticoesLista):

			listaOriginal = gerador_listas_random(tamanho)			

			inicio = 0
			fim = len(listaOriginal) - 1

			#quick sort
			t1 = datetime.datetime.now()
			algoritmos.quick_sort(list(listaOriginal), inicio, fim)
			t2 = datetime.datetime.now()
			tempo = (t2-t1).microseconds
			resultadosQuick.append(tempo)

			#merge sort
			t1 = datetime.datetime.now()
			listaOrdenadaMerge = algoritmos.merge_sort(listaOriginal)
			t2 = datetime.datetime.now()
			tempo = (t2-t1).microseconds
			resultadosMerge.append(tempo)
		
			#insertion sort
			t1 = datetime.datetime.now()
			algoritmos.insertion_sort(list(listaOriginal))
			t2 = datetime.datetime.now()
			tempo = (t2-t1).microseconds
			resultadosInsertion.append(tempo)
		
			#bubble sort
			t1 = datetime.datetime.now()
			algoritmos.bubble_sort(list(listaOriginal))
			t2 = datetime.datetime.now()
			tempo = (t2-t1).microseconds
			resultadosBubble.append(tempo)
		
			#heap sort
			t1 = datetime.datetime.now()
			algoritmos.heap_sort(list(listaOriginal))
			t2 = datetime.datetime.now()
			tempo = (t2-t1).microseconds
			resultadosHeap.append(tempo)
		
			#shell sort
			t1 = datetime.datetime.now()
			algoritmos.shell_sort(list(listaOriginal))
			t2 = datetime.datetime.now()
			tempo = (t2-t1).microseconds
			resultadosShell.append(tempo)
		
			#selection sort
			t1 = datetime.datetime.now()
			algoritmos.selection_sort(list(listaOriginal))
			t2 = datetime.datetime.now()
			tempo = (t2-t1).microseconds
			resultadosSelection.append(tempo)
		
			#bucket sort
			t1 = datetime.datetime.now()
			listaOrdenadaBucket = algoritmos.bucket_sort(listaOriginal)
			t2 = datetime.datetime.now()
			tempo = (t2-t1).microseconds
			resultadosBucket.append(tempo)
			pass

		print 'Fim:', time.strftime('%X')
		
		#Adicionando as listas com os resultados ao dicionário
		dictAlgoritmo['Quick-Sort'].append(resultadosQuick)
		dictAlgoritmo['Merge-Sort'].append(resultadosMerge)
		dictAlgoritmo['Insertion-Sort'].append(resultadosInsertion)
		dictAlgoritmo['Bubble-Sort'].append(resultadosBubble)
		dictAlgoritmo['Heap-Sort'].append(resultadosHeap)
		dictAlgoritmo['Shell-Sort'].append(resultadosShell)
		dictAlgoritmo['Selection-Sort'].append(resultadosSelection)
		dictAlgoritmo['Bucket-Sort'].append(resultadosBucket)
		pass

	#Escolher opcao(oes) para apresentacao de dados:
	resultados_output_visual(dictAlgoritmo) # terminal
	resultados_output_csv(dictAlgoritmo) # ficheiros CSV
	pass

main()